{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Path in a Grid with Obstacles Elimination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格中的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m * n</code>&nbsp;的网格，其中每个单元格不是&nbsp;<code>0</code>（空）就是&nbsp;<code>1</code>（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。</p>\n",
    "\n",
    "<p>如果您 <strong>最多</strong> 可以消除 <code>k</code> 个障碍物，请找出从左上角 <code>(0, 0)</code> 到右下角 <code>(m-1, n-1)</code> 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://pic.leetcode.cn/1700710956-kcxqcC-img_v3_025f_d55a658c-8f40-464b-800f-22ccd27cc9fg.jpg\" style=\"width: 243px; height: 404px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：\n",
    "</strong>不消除任何障碍的最短路径是 10。\n",
    "消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 <code>(0,0) -&gt; (0,1) -&gt; (0,2) -&gt; (1,2) -&gt; (2,2) -&gt; <strong>(3,2)</strong> -&gt; (4,2)</code>.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://pic.leetcode.cn/1700710701-uPqkZe-img_v3_025f_0edd50fb-8a70-4a42-add0-f602caaad35g.jpg\" style=\"width: 243px; height: 244px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>我们至少需要消除两个障碍才能找到这样的路径。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>grid.length&nbsp;== m</code></li>\n",
    "\t<li><code>grid[0].length&nbsp;== n</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 40</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= m*n</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;是&nbsp;<code>0</code>&nbsp;或<strong>&nbsp;</strong><code>1</code></li>\n",
    "\t<li><code>grid[0][0] == grid[m-1][n-1] == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-path-in-a-grid-with-obstacles-elimination](https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-path-in-a-grid-with-obstacles-elimination](https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]\\n1', '[[0,1,1],[1,1,1],[1,0,0]]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        target = (rows-1, cols-1)\n",
    "        \n",
    "        state = (0,0,k)\n",
    "        seen = set([state])\n",
    "        queue = collections.deque([(0,state)])\n",
    "        \n",
    "        while queue:\n",
    "            step, (row, col, new_k) = queue.popleft()\n",
    "            \n",
    "            if (row, col) == target:\n",
    "                return step\n",
    "            \n",
    "            for new_row, new_col in [(row, col+1), (row+1, col), (row-1, col), (row, col-1)]:\n",
    "                if 0 <= new_row < rows and 0<= new_col < cols:\n",
    "                    new_elimination = new_k - grid[new_row][new_col]\n",
    "                    new_state = (new_row, new_col, new_elimination)\n",
    "                    if new_elimination >= 0 and new_state not in seen:\n",
    "                        seen.add(new_state)\n",
    "                        queue.append((step+1, new_state))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        R,C = len(grid), len(grid[0])\n",
    "        if R==1 and C==1:\n",
    "            return 0\n",
    "        d = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def go(r,c,k):\n",
    "            for dr,dc in d:\n",
    "                nr,nc = r+dr,c+dc\n",
    "                if 0<=nr<R and 0<=nc<C:\n",
    "                    if grid[nr][nc]:\n",
    "                        if k:\n",
    "                            yield(nr,nc,k-1)\n",
    "                    else:\n",
    "                        yield((nr,nc,k))\n",
    "        BFS = [(0,0,k)]\n",
    "        step = 0\n",
    "        been = {(0,0):k}\n",
    "        while(BFS):\n",
    "            step+=1\n",
    "            BNext = []\n",
    "            for p in BFS:\n",
    "                for np in go(*p):\n",
    "                    r,c,k = np\n",
    "                    if (r,c) in been and been[r,c]>=k:\n",
    "                        continue\n",
    "                    if r == R-1 and c==C-1:\n",
    "                        return step\n",
    "                    BNext.append(np)\n",
    "                    been[r,c] = k\n",
    "            BFS = BNext\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m ,n = len(grid), len(grid[0])\n",
    "        rec = [[k + 1] * n for _ in range(m)]\n",
    "        from collections import deque\n",
    "        queue = deque([(0, 0, 0, 0)])\n",
    "        while queue:\n",
    "            i, j, step, t = queue.popleft()\n",
    "            if t > rec[i][j]:   continue\n",
    "            if i == m - 1 and j == n - 1:   return step\n",
    "            for di, dj in ((1, 0),(0, 1),(-1, 0),(0, -1)):\n",
    "                ii, jj = i + di, j + dj\n",
    "                if 0 <= ii < m and 0 <= jj < n:\n",
    "                    temp = t\n",
    "                    if grid[ii][jj] == 1:   temp += 1\n",
    "                    if temp < rec[ii][jj]:\n",
    "                        rec[ii][jj] = temp\n",
    "                        queue.append((ii, jj, step + 1, temp))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k,queue,count,visited=min(k, m+n-3),collections.deque([(0,0,0)]),0,collections.defaultdict(lambda :float('inf'))\n",
    "        if m+n-3==k or (m==1 and n==1):\n",
    "            return m+n-2\n",
    "        while queue:\n",
    "            count+=1\n",
    "            for _ in range(len(queue)):\n",
    "                i,j,l=queue.popleft()\n",
    "                if visited[(i,j)]<l:\n",
    "                    continue\n",
    "                for x,y in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                    if 0<=x<len(grid) and 0<=y<len(grid[0]) and l<visited[(x,y)]:\n",
    "                        if grid[x][y]==0:\n",
    "                            queue.append((x,y,l))\n",
    "                            visited[(x,y)]=l\n",
    "                        elif l+1<=k and l+1<visited[(x,y)]:\n",
    "                            queue.append((x,y,l+1))\n",
    "                            visited[(x,y)]=l+1\n",
    "                        if (m-1,n-1) in visited:\n",
    "                            return count\n",
    "        return 0 if len(grid)==1 and len(grid[0])==1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "\n",
    "        seen = [[float('inf') for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        seen[0][0] = 0\n",
    "        queue = [[0, 0, 0]]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        step = 0\n",
    "\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                point = queue.pop(0)\n",
    "                row = point[0]\n",
    "                col = point[1]\n",
    "                if (row == m - 1) and (col == n - 1):\n",
    "                    return step\n",
    "                \n",
    "                for i in self.direction:\n",
    "                    r = row + i[0]\n",
    "                    c = col + i[1]\n",
    "                    if r >= 0 and r <= m - 1 and c >= 0 and c <= n - 1:\n",
    "                        ost = point[2] + grid[r][c]\n",
    "                        if ost >= seen[r][c] or ost > k:\n",
    "                            continue\n",
    "                        seen[r][c] = ost\n",
    "                        queue.append((r, c, ost))\n",
    "            step += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid, k) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        \n",
    "        k, queue, count, visited = min(k, m + n - 3), collections.deque([(0, 0, 0)]), 0, collections.defaultdict(\n",
    "            lambda: float('inf'))\n",
    "\n",
    "        if m + n - 3 == k or (m == 1 and n == 1):\n",
    "            return m + n - 2\n",
    "        \n",
    "        \n",
    "\n",
    "        while queue:\n",
    "\n",
    "            count += 1\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                i, j, l = queue.popleft()\n",
    "\n",
    "                if visited[(i, j)] < l:\n",
    "                    continue\n",
    "\n",
    "                for x, y in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and l < visited[(x, y)]:\n",
    "                        if grid[x][y] == 0:\n",
    "                            queue.append((x, y, l))\n",
    "                            visited[(x, y)] = l\n",
    "                        elif l + 1 <= k and l + 1 < visited[(x, y)]:\n",
    "                            queue.append((x, y, l + 1))\n",
    "                            visited[(x, y)] = l + 1\n",
    "                        if (m - 1, n - 1) in visited:\n",
    "                            return count\n",
    "        \n",
    "        if len(grid) == 1 and len(grid[0]) == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestPath(self, grid, k) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        k, queue, count, visited = min(k, m + n - 3), collections.deque([(0, 0, 0)]), 0, collections.defaultdict( lambda: float('inf'))\n",
    "\n",
    "        while queue:\n",
    "            count += 1\n",
    "            \n",
    "            for _ in range(len(queue)):\n",
    "\n",
    "                i, j, l = queue.popleft()\n",
    "\n",
    "               \n",
    "                    \n",
    "                for x, y in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "\n",
    "                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and l < visited[(x, y)]:\n",
    "\n",
    "                        if grid[x][y] == 0:\n",
    "                            queue.append((x, y, l))\n",
    "                            visited[(x, y)] = l\n",
    "\n",
    "                        elif l + 1 <= k and l + 1 < visited[(x, y)]:\n",
    "                            queue.append((x, y, l + 1))\n",
    "                            visited[(x, y)] = l + 1\n",
    "\n",
    "                        if (m - 1, n - 1) in visited:\n",
    "                            return count\n",
    "\n",
    "        if len(grid) == 1 and len(grid[0]) == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "\n",
    "        if not grid or not grid[0]: return -1\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        if rows == 1 and cols == 1:\n",
    "            return 0\n",
    "        # 如果可消除 m + n - 3 个障碍物以上，则直接可得最短路径m + n - 2\n",
    "        if k >= rows + cols - 3:\n",
    "            return rows + cols - 2\n",
    "\n",
    "        visited = set([(0, 0, k)])         #记录走的路径及剩余可消除障碍的数量\n",
    "        que = collections.deque([(0, 0, k)])\n",
    "        step = 0\n",
    "\n",
    "        while len(que) > 0:\n",
    "            step += 1\n",
    "            q_len = len(que)\n",
    "            for _ in range(q_len):\n",
    "                x, y, remain_k = que.popleft()\n",
    "                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < rows and 0 <= ny < cols:\n",
    "                        # 无障碍且未走过\n",
    "                        if grid[nx][ny] == 0 and (nx, ny, remain_k) not in visited:\n",
    "                            # 到达最后一步\n",
    "                            if nx == rows - 1 and ny == cols - 1:\n",
    "                                return step\n",
    "                            que.append((nx, ny, remain_k))\n",
    "                            visited.add((nx, ny, remain_k))\n",
    "                        # 有障碍，障碍可消除且未走过\n",
    "                        if grid[nx][ny] == 1 and remain_k > 0 and (nx, ny, remain_k - 1) not in visited:\n",
    "                            que.append((nx, ny, remain_k - 1))\n",
    "                            visited.add((nx, ny, remain_k - 1))\n",
    "                            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "\n",
    "        if not grid or not grid[0]: return -1\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        if rows == 1 and cols == 1:\n",
    "            return 0\n",
    "        # 如果可消除 m + n - 3 个障碍物以上，则直接可得最短路径m + n - 2\n",
    "        if k >= rows + cols - 3:\n",
    "            return rows + cols - 2\n",
    "\n",
    "        visited = set([(0, 0, k)])         #记录走的路径及剩余可消除障碍的数量\n",
    "        que = collections.deque([(0, 0, k)])\n",
    "        step = 0\n",
    "\n",
    "        while len(que) > 0:\n",
    "            step += 1\n",
    "            q_len = len(que)\n",
    "            for _ in range(q_len):\n",
    "                x, y, remain_k = que.popleft()\n",
    "                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < rows and 0 <= ny < cols:\n",
    "                        # 无障碍且未走过\n",
    "                        if grid[nx][ny] == 0 and (nx, ny, remain_k) not in visited:\n",
    "                            # 到达最后一步\n",
    "                            if nx == rows - 1 and ny == cols - 1:\n",
    "                                return step\n",
    "                            que.append((nx, ny, remain_k))\n",
    "                            visited.add((nx, ny, remain_k))\n",
    "                        # 有障碍，障碍可消除且未走过\n",
    "                        if grid[nx][ny] == 1 and remain_k > 0 and (nx, ny, remain_k - 1) not in visited:\n",
    "                            que.append((nx, ny, remain_k - 1))\n",
    "                            visited.add((nx, ny, remain_k - 1))\n",
    "                            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        if k >= R + C - 2:      #直接贴边走  走了 R + C - 2个步  中间经过 R+C-3个点\n",
    "            return R + C - 2\n",
    "        k = min(k, R + C - 3)   #中间最多清楚 R + C - 3个障碍，贴边走就能到\n",
    "        dirs = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        visited = [[[False for _ in range(k + 1)] for _ in range(C)] for _ in range(R)]\n",
    "        queue = []\n",
    "        visited[0][0][k] = True     #坐标 0,0 还剩k步（还可以开挂k次）可以用\n",
    "        queue.append([0,0,k])\n",
    "        level = 1\n",
    "        while queue:                                #记忆化 BFS 波纹法\n",
    "            cur_len = len(queue)\n",
    "            for _ in range(cur_len):                #波纹法\n",
    "                r,c,remain_step = queue.pop(0)\n",
    "                for dr,dc in dirs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if 0 <= nr < R and 0 <= nc < C:\n",
    "                        if grid[nr][nc] == 0 and visited[nr][nc][remain_step] == False: #下一步很顺利，是个0，不是障碍\n",
    "                            if nr == R-1 and nc == C-1:                 #到最右下角终点了\n",
    "                                return level\n",
    "                            else:\n",
    "                                visited[nr][nc][remain_step] = True     #中途普通的位置\n",
    "                                queue.append([nr, nc, remain_step])\n",
    "                        elif grid[nr][nc] == 1 and remain_step > 0 and visited[nr][nc][remain_step - 1] == False:   #下一步是个障碍\n",
    "                            visited[nr][nc][remain_step - 1] = True\n",
    "                            queue.append([nr, nc, remain_step - 1])\n",
    "            level += 1\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        inf = float(\"inf\")\n",
    "        visit = [[inf]*n for _ in range(m)]\n",
    "        stack = [[0, 0, 0, 0]]\n",
    "        while stack:\n",
    "            dis, i, j, c = heapq.heappop(stack)\n",
    "            if visit[i][j] <= c:\n",
    "                continue\n",
    "            if c > k:\n",
    "                continue\n",
    "            visit[i][j] = c\n",
    "            if [i, j] == [m-1, n-1]:\n",
    "                return dis\n",
    "            for a, b in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:\n",
    "                if 0<=a<m and 0<=b<n:\n",
    "                    heapq.heappush(stack, [dis+1, a, b, c+grid[a][b]])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def check_valid_and_update_history(self,next_r,next_c,k):\n",
    "        next_k = k-self.grid[next_r][next_c]\n",
    "        if (f\"{next_r},{next_c}\" in self.history_opimal and self.history_opimal[f\"{next_r},{next_c}\"]<next_k) or (f\"{next_r},{next_c}\" not in self.history_opimal and next_k>=0):\n",
    "            self.history_opimal[f\"{next_r},{next_c}\"] = next_k\n",
    "            self.next_state[f\"{next_r},{next_c}\"] = next_k\n",
    "            if next_r==self.h-1 and next_c==self.w-1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        self.grid = grid\n",
    "        h,w = len(grid),len(grid[0])\n",
    "        \n",
    "        if h==1 and w==1:\n",
    "            return 0\n",
    "        self.h = h\n",
    "        self.w=w\n",
    "        self.DP_state = {f\"{0},{0}\":k}\n",
    "        self.history_opimal ={f\"{0},{0}\":k}\n",
    "        step = 0         \n",
    "        while self.DP_state:\n",
    "            step+=1\n",
    "            self.next_state = {}\n",
    "            for key,v in self.DP_state.items():\n",
    "                r,c = key.split(\",\")\n",
    "                r,c = int(r),int(c)\n",
    "                if r>0 and self.check_valid_and_update_history(r-1,c,v):\n",
    "                    return step\n",
    "                if c>0 and self.check_valid_and_update_history(r,c-1,v):\n",
    "                    return step\n",
    "                if r<h-1 and self.check_valid_and_update_history(r+1,c,v):\n",
    "                    return step\n",
    "                if c<w-1 and self.check_valid_and_update_history(r,c+1,v):\n",
    "                    return step\n",
    "            self.DP_state = self.next_state\n",
    "        return -1\n",
    "                    \n",
    "    \n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestPath(self, grid, k: int) -> int:\n",
    "#         rows, cols = len(grid), len(grid[0])\n",
    "#         target = (rows-1, cols-1)\n",
    "#         if k >= rows + cols - 2:\n",
    "#             return rows + cols - 2\n",
    "#         state = (0, 0, k)\n",
    "#         queue = collections.deque([(0, state)])\n",
    "#         seen = set([state])\n",
    "#         def next_step(i,j):\n",
    "#             dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "#             for dx, dy in dirs:\n",
    "#                 x, y = i+dx, j+dy\n",
    "#                 if 0<=x<rows and 0<=y<cols:\n",
    "#                     yield x, y\n",
    "#         while queue:\n",
    "#             steps, (row, col, k) = queue.popleft()\n",
    "#             if (row, col) == target:\n",
    "#                 return steps\n",
    "#             for x, y in next_step(row, col):\n",
    "#                 new_k = k-grid[x][y]\n",
    "#                 new_state = (x,y,new_k)\n",
    "#                 if new_k >= 0 and new_state not in seen:\n",
    "#                     seen.add(new_state)\n",
    "#                     queue.append((steps+1, new_state))\n",
    "#         return -1\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        target = (rows - 1, cols - 1)\n",
    "\n",
    "        def manhattan_dist(row, col):\n",
    "            return target[0] - row + target[1] - col\n",
    "\n",
    "        def next_step(i,j):\n",
    "            dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "            for dx, dy in dirs:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0<=x<rows and 0<=y<cols:\n",
    "                    yield x, y\n",
    "\n",
    "        state = (0, 0, k)\n",
    "        queue = [(manhattan_dist(0, 0), 0, state)]\n",
    "        seen = set([state])\n",
    "\n",
    "        while queue:\n",
    "            estimation, steps, (row, col, k) = heapq.heappop(queue)\n",
    "            # we can reach the target in the shortest path (manhattan distance),\n",
    "            #   even if the remaining steps are all obstacles\n",
    "            remain_min_dist = estimation - steps\n",
    "            if manhattan_dist(row, col) <= k:\n",
    "                return estimation\n",
    "\n",
    "            for x, y in next_step(row, col):\n",
    "                new_k = k - grid[x][y]\n",
    "                new_state = (x, y, new_k)\n",
    "\n",
    "                # if the next direction is worth exploring\n",
    "                if new_k >= 0 and new_state not in seen:\n",
    "                    seen.add(new_state)\n",
    "                    new_estimation = manhattan_dist(x, y) + steps + 1\n",
    "                    heapq.heappush(queue, (new_estimation, steps + 1, new_state))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return 0\n",
    "        \n",
    "        k = min(k, m + n - 3)\n",
    "        direct = [(-1, 0), (0, 1), (0, -1), (1, 0)]\n",
    "        visited = [[-1] * n for _ in range(m)]\n",
    "        visited[0][0] = k\n",
    "        q = [(0,0,k)]\n",
    "        step = 0\n",
    "        while len(q) > 0:\n",
    "            step += 1\n",
    "            cnt = len(q)\n",
    "            for _ in range(cnt):\n",
    "                x, y, rest = q.pop(0)\n",
    "                for dx, dy in direct:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        if nx == m-1 and ny==n-1:\n",
    "                            return step\n",
    "\n",
    "                        new_rest = rest - grid[nx][ny]\n",
    "                        if  visited[nx][ny] >= new_rest:\n",
    "                            continue\n",
    "                        elif new_rest >= 0:\n",
    "                            q.append((nx, ny, new_rest))\n",
    "                            visited[nx][ny] = new_rest\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def Score(self, cur):\n",
    "        return (self.r - cur[1] - 1) + (self.c - cur[2] - 1) + cur[4] + 1\n",
    "\n",
    "    def shortestPath(self, grid, k):\n",
    "        self.k = k\n",
    "        self.r = len(grid)\n",
    "        self.c = len(grid[0])\n",
    "        from queue import PriorityQueue\n",
    "        que = PriorityQueue()\n",
    "        que.put((0, 0, 0, k, 0), False)\n",
    "        visited = [[-1 for i in range(self.c)] for j in range(self.r)]\n",
    "        while not que.empty():\n",
    "            cur = que.get(False)\n",
    "            #print('visit:', cur)\n",
    "            visited[cur[1]][cur[2]] = cur[3]\n",
    "            if cur[1] == self.r - 1 and cur[2] == self.c - 1:\n",
    "                return cur[4]\n",
    "            if cur[1] > 0:\n",
    "                kk = cur[3]\n",
    "                if grid[cur[1] - 1][cur[2]] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and visited[cur[1] - 1][cur[2]] < kk:\n",
    "                    que.put((self.Score(cur), cur[1] - 1, cur[2], kk, cur[4] + 1), False)\n",
    "                    visited[cur[1] - 1][cur[2]] = kk\n",
    "            if cur[1] < self.r - 1:\n",
    "                kk = cur[3]\n",
    "                if grid[cur[1] + 1][cur[2]] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and visited[cur[1] + 1][cur[2]] < kk:\n",
    "                    que.put((self.Score(cur), cur[1] + 1, cur[2], kk, cur[4] + 1), False)\n",
    "                    visited[cur[1] + 1][cur[2]] = kk\n",
    "            if cur[2] > 0:\n",
    "                kk = cur[3]\n",
    "                if grid[cur[1]][cur[2] - 1] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and visited[cur[1]][cur[2] - 1] < kk:\n",
    "                    que.put((self.Score(cur), cur[1], cur[2] - 1, kk, cur[4] + 1), False)\n",
    "                    visited[cur[1]][cur[2] - 1] = kk\n",
    "            if cur[2] < self.c - 1:\n",
    "                kk = cur[3]\n",
    "                if grid[cur[1]][cur[2] + 1] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and visited[cur[1]][cur[2] + 1] < kk:\n",
    "                    que.put((self.Score(cur), cur[1], cur[2] + 1, kk, cur[4] + 1), False)\n",
    "                    visited[cur[1]][cur[2] + 1] = kk\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if k >= m + n - 2:\n",
    "            return m + n - 2\n",
    "        q1 = {(0,0): 0}\n",
    "        q2 = {(m-1,n-1): 0}\n",
    "        step = 0\n",
    "        visited1 = {}\n",
    "        visited2 = {}\n",
    "        while q1 and q2:\n",
    "            if len(q1) > len(q2):\n",
    "                q1,q2 = q2,q1 \n",
    "                visited1, visited2 = visited2, visited1\n",
    "            queue = {}\n",
    "            for row,col in q1:\n",
    "                if (row, col) in q2:\n",
    "                    total_used = q1[(row,col)] + q2[(row, col)] - grid[row][col]\n",
    "                    if total_used <= k:\n",
    "                        return step\n",
    "                visited1[(row, col)] = q1[(row, col)]\n",
    "                for r,c in [(row-1, col), (row+1, col), (row, col+1), (row, col-1)]:\n",
    "                    if 0<=r<m and 0<=c<n:\n",
    "                        used = q1[(row, col)] + grid[r][c]\n",
    "                        if used <= k and ((r,c) not in visited1 or used < visited1[(r,c)]) and ((r,c) not in queue or used < queue[(r,c)]):\n",
    "                            queue[(r,c)] = used\n",
    "            q1 = queue\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if k >= m + n - 3:\n",
    "            return m + n - 2\n",
    "        queue = [(0, 0, k)]\n",
    "        visited = {(0, 0, k)}\n",
    "        steps = 0\n",
    "        while queue:\n",
    "            steps += 1\n",
    "            tmp = []\n",
    "            for x, y, rest in queue:\n",
    "                for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if not 0 <= i < m or not 0 <= j < n:\n",
    "                        continue\n",
    "                    if grid[i][j] == 0 and (i, j, rest) not in visited:\n",
    "                        if i == m - 1 and j == n - 1:\n",
    "                            return steps\n",
    "                        tmp.append((i, j, rest))\n",
    "                        visited.add((i, j, rest))\n",
    "                    elif grid[i][j] == 1 and rest > 0 and (i, j, rest - 1) not in visited:\n",
    "                        tmp.append((i, j, rest - 1))\n",
    "                        visited.add((i, j, rest - 1))\n",
    "            queue = tmp\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if k >= m+n-3:\n",
    "            return m + n - 2\n",
    "        queue = collections.deque([(0, 0, k, 0)])\n",
    "        visited = set((0, 0, k))\n",
    "        while queue:\n",
    "            x, y, tmpk, step = queue.popleft()\n",
    "            if x == m-1 and y == n-1:\n",
    "                return step\n",
    "            for nx, ny in ((x-1, y), (x+1, y), (x, y+1), (x, y-1)):\n",
    "                if 0 <=nx < m and 0 <= ny <n:\n",
    "                    if tmpk > 0 and (nx, ny, tmpk-1) not in visited and grid[nx][ny] == 1:\n",
    "                        queue.append((nx, ny, tmpk-1, step + 1))\n",
    "                        visited.add((nx, ny, tmpk-1))\n",
    "                    elif (nx, ny, tmpk) not in visited and grid[nx][ny] == 0:\n",
    "                        queue.append((nx, ny, tmpk, step+1))\n",
    "                        visited.add((nx, ny, tmpk))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      if k > m + n - 3 or k > sum(r.count(1) for r in grid):\n",
    "        return m + n - 2\n",
    "      q = deque([(0, 0, k)])\n",
    "      dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "      steps = 0\n",
    "      visited = set()\n",
    "      visited.add((0, 0, k))\n",
    "      while len(q) > 0:\n",
    "        l = len(q)\n",
    "        while l > 0:\n",
    "          x, y, cnt = q.popleft()\n",
    "          if x == m - 1 and y == n - 1:\n",
    "            return steps\n",
    "          l -= 1\n",
    "          for dx, dy in dirs:\n",
    "            x1 = x + dx\n",
    "            y1 = y + dy\n",
    "            if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n:\n",
    "              continue\n",
    "            if grid[x1][y1] == 1 and (x1, y1, cnt - 1) not in visited and cnt > 0:\n",
    "              q.append((x1, y1, cnt - 1))\n",
    "              visited.add((x1, y1, cnt - 1))\n",
    "            elif grid[x1][y1] == 0 and (x1, y1, cnt) not in visited:\n",
    "              q.append((x1, y1, cnt))\n",
    "              visited.add((x1, y1, cnt))\n",
    "        steps += 1\n",
    "      \n",
    "      return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        #nodes = 40 * 40\n",
    "        #dp i j k 到达 i j 删除k 40 * 40* 80\n",
    "        #状态搜索\n",
    "        self.k = k\n",
    "        self.n, self.m = len(grid), len(grid[0])\n",
    "        self.maxBreak = min(k, self.n + self.m) + 1\n",
    "        self.record = {}#(i, j) []\n",
    "        self.dfs(grid, 0, 0, 0, 0)\n",
    "        if (self.n-1, self.m-1) not in self.record:\n",
    "            return -1\n",
    "        else:\n",
    "            return min(self.record[(self.n-1, self.m-1)])\n",
    "\n",
    "    def dfs(self, grid, x, y, breaks, steps):\n",
    "        if breaks > self.k or breaks > x + y:\n",
    "            return\n",
    "        if (x, y) not in self.record:\n",
    "            self.record[(x, y)] = [10000] * self.maxBreak\n",
    "        elif self.record[(x, y)][breaks] <= steps:\n",
    "            return\n",
    "        self.record[(x, y)][breaks] = steps\n",
    "\n",
    "        if x > 0:\n",
    "            if grid[x-1][y] == 1:\n",
    "                self.dfs(grid, x-1, y, breaks + 1, steps + 1)\n",
    "            else:\n",
    "                self.dfs(grid, x-1, y, breaks, steps + 1)\n",
    "        if y > 0:\n",
    "            if grid[x][y-1] == 1:\n",
    "                self.dfs(grid, x, y-1, breaks + 1, steps + 1)\n",
    "            else:\n",
    "                self.dfs(grid, x, y-1, breaks, steps + 1)\n",
    "        if x < self.n - 1:\n",
    "            if grid[x+1][y] == 1:\n",
    "                self.dfs(grid, x+1, y, breaks + 1, steps + 1)\n",
    "            else:\n",
    "                self.dfs(grid, x+1, y, breaks, steps + 1)\n",
    "        if y < self.m -1:\n",
    "            if grid[x][y+1] == 1:\n",
    "                self.dfs(grid, x, y+1, breaks + 1, steps + 1)\n",
    "            else:\n",
    "                self.dfs(grid, x, y+1, breaks, steps + 1)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        self.vis = {(0, 0): [(0, 0)]}\n",
    "        self.grid = grid\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "        self.k = k\n",
    "        if self.k >= self.m + self.n - 2:\n",
    "            return self.m + self.n - 2\n",
    "        self.ans = float(\"inf\")\n",
    "        self.dfs((0,0), 0, 0)\n",
    "        if self.ans == float(\"inf\"):\n",
    "            self.ans = -1\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, point, cost, step):\n",
    "        x, y = point\n",
    "        if (x, y) == (self.m-1, self.n-1):\n",
    "            self.ans = min(self.ans, step)\n",
    "            return\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        for dir in dirs:\n",
    "            dx, dy = dir\n",
    "            nx = x + dx\n",
    "            ny = y + dy\n",
    "            if 0 <= nx < self.m and 0 <= ny < self.n:\n",
    "                step1 = step + 1\n",
    "                cost1 = cost\n",
    "                if self.grid[nx][ny] == 1:\n",
    "                    cost1 += 1\n",
    "                if cost1 > self.k:\n",
    "                    continue\n",
    "                if (nx, ny) in self.vis:\n",
    "                    arr = self.vis[(nx, ny)]\n",
    "                    flag = False\n",
    "                    for i, (cost2, step2) in enumerate(arr):\n",
    "                        if cost1 >= cost2 and step1 >= step2:\n",
    "                            flag = True\n",
    "                            break\n",
    "                    \n",
    "                    if flag:\n",
    "                        continue\n",
    "                    flag2 = False\n",
    "                    for i, (cost2, step2) in enumerate(arr):\n",
    "                        if cost1 <= cost2 and step1 <= step2:\n",
    "                            flag2 = True\n",
    "                            arr[i] = (cost1, step1)\n",
    "                    if not flag2:\n",
    "                        self.vis[(nx, ny)].append((cost1, step1))\n",
    "                    self.dfs((nx, ny), cost1, step1)\n",
    "                else:\n",
    "                    self.vis[(nx, ny)] = [(cost1, step1)]\n",
    "                    self.dfs((nx, ny), cost1, step1)\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from queue import Queue\n",
    "# def printTrace(last_pos:dict, end_pos:str):\n",
    "#     result = []\n",
    "#     result.append(end_pos)\n",
    "#\n",
    "#     while str(end_pos) in last_pos:\n",
    "#         result.append(last_pos[end_pos])\n",
    "#         end_pos = last_pos[end_pos]\n",
    "#         # print(end_pos)\n",
    "#\n",
    "#     for i in range(len(result) - 1, -1, -1):\n",
    "#         print(result[i])\n",
    "\n",
    "def is_legal_pos(i, j, m, n):\n",
    "    return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        # mp = {}\n",
    "        # 状态标志(剩余可推翻的障碍物数，x,y)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = Queue()\n",
    "        visited = set()\n",
    "        q.put_nowait((k, 0, 0))\n",
    "        visited.add((k, 0, 0))\n",
    "        pos_visited=  set()\n",
    "        pos_visited.add((0, 0))\n",
    "        max_left_walls = {}\n",
    "        max_left_walls[\"0#0\"] = k\n",
    "\n",
    "        dir4 = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        step = 0\n",
    "        while not q.empty():\n",
    "            need_add_q = []\n",
    "            while not q.empty():\n",
    "                cur = q.get_nowait()\n",
    "                if cur[1] == m - 1 and cur[2] == n - 1:\n",
    "                    # printTrace(mp, str(cur[0]) + '#' + str(cur[1]) + '#' + str(cur[2]))\n",
    "                    return step\n",
    "                left_wall = cur[0]\n",
    "                for dir in dir4:\n",
    "                    next_i, next_j = cur[1] + dir[0], cur[2] + dir[1]\n",
    "\n",
    "                    \n",
    "                    if not is_legal_pos(next_i, next_j, m, n):\n",
    "                        continue\n",
    "                    if grid[next_i][next_j] == 1:\n",
    "                        if left_wall != 0:\n",
    "                            if (next_i, next_j) in pos_visited:\n",
    "                                if str(next_i) + \"#\" + str(next_j) in max_left_walls and max_left_walls[\n",
    "                                    str(next_i) + \"#\" + str(next_j)] >= left_wall - 1:\n",
    "                                    continue\n",
    "                            \n",
    "                            next_state = (left_wall - 1, next_i, next_j)\n",
    "                            if not next_state in visited:\n",
    "                                pos_visited.add((next_i, next_j))\n",
    "                                max_left_walls[str(next_i) + \"#\" + str(next_j)] = left_wall - 1\n",
    "                                need_add_q.append(next_state)\n",
    "                                visited.add(next_state)\n",
    "                                # mp[str(next_state[0]) + '#' + str(next_state[1]) + '#' + str(next_state[2])] = str(cur[0]) + '#' + str(cur[1]) + '#' + str(cur[2])\n",
    "                        continue\n",
    "                    if (next_i, next_j) in pos_visited:\n",
    "                        if str(next_i) + \"#\" + str(next_j) in max_left_walls and max_left_walls[\n",
    "                            str(next_i) + \"#\" + str(next_j)] >= left_wall:\n",
    "                            continue\n",
    "                    next_state = (left_wall, next_i, next_j)\n",
    "                    if not next_state in visited:\n",
    "                        pos_visited.add((next_i, next_j))\n",
    "                        max_left_walls[str(next_i) + \"#\" + str(next_j)] = left_wall\n",
    "                        need_add_q.append(next_state)\n",
    "                        visited.add(next_state)\n",
    "                        # mp[str(next_state[0]) + '#' + str(next_state[1]) + '#' + str(next_state[2])] = str(cur[0]) + '#' + str(cur[1]) + '#' + str(cur[2])\n",
    "            for tt in need_add_q:\n",
    "                q.put_nowait(tt)\n",
    "\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "# print(Solution().shortestPath([[0, 1, 1], [1, 1, 1], [1, 0, 0]], 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        # bfs\n",
    "        queue = collections.deque()\n",
    "        queue.append((0,0,k))\n",
    "        m,n = len(grid),len(grid[0])\n",
    "\n",
    "        step = 0\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            len_ = len(queue)\n",
    "            layer_dict = {}\n",
    "            for _ in range(len_):\n",
    "                x,y,c = queue.popleft()\n",
    "                if x == m-1 and y==n-1:\n",
    "                    return step \n",
    "\n",
    "                visited.add((x,y,c))\n",
    "\n",
    "                for add_x, add_y in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                    new_x,new_y = x+add_x,y+add_y \n",
    "\n",
    "                    if new_x<0 or new_y<0 or new_x>=m or new_y>=n:\n",
    "                        continue\n",
    "                    \n",
    "                    if grid[new_x][new_y] == 0:\n",
    "                        resblock = c\n",
    "                    elif grid[new_x][new_y] == 1:\n",
    "                        resblock = c-1\n",
    "                    if resblock>=0:\n",
    "                        if (new_x,new_y, resblock) in visited:\n",
    "                            continue\n",
    "                        if (new_x,new_y) in layer_dict:\n",
    "                            layer_dict[(new_x,new_y)] = max(layer_dict[(new_x,new_y)],resblock)\n",
    "                        else:\n",
    "                            layer_dict[(new_x,new_y)] = resblock\n",
    "                    \n",
    "            for x,y in layer_dict:\n",
    "                queue.append((x,y,layer_dict[(x,y)]))\n",
    "\n",
    "            step += 1\n",
    "\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        print(((1,2),(2,3)) == ((2,3),(1,2)))\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if k >= m + n -3:\n",
    "            return m + n - 2\n",
    "        \n",
    "\n",
    "        visit = set()\n",
    "        visit.add((0,0,k))\n",
    "        @cache\n",
    "        def dfs1(x,y,k):\n",
    "            # print(x,y,k) \n",
    "            # print(visit)           \n",
    "            if x == m-1 and y == n-1:\n",
    "                return 0\n",
    "            if grid[x][y]:\n",
    "                if k > 0:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    return inf\n",
    "            # visit.add((x,y,k))\n",
    "            ans = inf\n",
    "            for dx,dy in [(1,0),(0,1),(0,-1),(-1,0)]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and (nx,ny,k) not in visit:\n",
    "                # if x < 0 or x >= m or y < 0 or y >= n or (x,y,k) in visit or (k <= 0 and grid[x][y]):   \n",
    "                    visit.add((nx,ny,k))            \n",
    "                    ans = min(ans,1+dfs1(nx,ny,k))\n",
    "                    visit.remove((nx,ny,k))  \n",
    "            # visit.remove((x,y,k))\n",
    "            # print(visit)\n",
    "            # print(x,y,k,ans)\n",
    "            return ans\n",
    "        visit = set()\n",
    "        visit.add((0,0,k))\n",
    "        @cache\n",
    "        def dfs2(x,y,k):\n",
    "            # print(x,y,k) \n",
    "            # print(visit)           \n",
    "            if x == m-1 and y == n-1:\n",
    "                return 0\n",
    "            if grid[x][y]:\n",
    "                if k > 0:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    return inf\n",
    "            # visit.add((x,y,k))\n",
    "            ans = inf\n",
    "            for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and (nx,ny,k) not in visit:\n",
    "                # if x < 0 or x >= m or y < 0 or y >= n or (x,y,k) in visit or (k <= 0 and grid[x][y]):   \n",
    "                    visit.add((nx,ny,k))            \n",
    "                    ans = min(ans,1+dfs2(nx,ny,k))\n",
    "                    visit.remove((nx,ny,k))  \n",
    "            # visit.remove((x,y,k))\n",
    "            # print(visit)\n",
    "            # print(x,y,k,ans)\n",
    "            return ans\n",
    "        res = min(dfs1(0,0,k),dfs2(0,0,k))\n",
    "        # print(dfs.cache_out())\n",
    "        return res if res != inf else -1\n",
    "\n",
    "        # visit.add((0,0,k))\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(x,y,k):\n",
    "        #     if x == m-1 and y == n-1:\n",
    "        #         return 0\n",
    "        #     ans = inf\n",
    "        #     for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "        #         nx,ny = x+dx,y+dy\n",
    "        #         if 0<=nx<m and 0<=ny<n:\n",
    "        #             # visit.add((nx,ny,k-1))\n",
    "        #             if grid[nx][ny]:  \n",
    "        #                 if k > 0 and (nx,ny,k-1) not in visit:   \n",
    "        #                     visit.add((nx,ny,k-1))                   \n",
    "        #                     ans = min(ans,1+dfs(nx,ny,k-1))\n",
    "        #                     visit.remove((nx,ny,k-1))  \n",
    "        #             elif (nx,ny,k) not in visit:\n",
    "        #                 visit.add((nx,ny,k))\n",
    "        #                 ans = min(ans,1+dfs(nx,ny,k))\n",
    "        #                 visit.remove((nx,ny,k))\n",
    "        #     # print(x,y,k,ans)\n",
    "        #     return ans\n",
    "        # res = dfs(0,0,k)\n",
    "        # return res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n, dp = len(grid), len(grid[0]), [[0,0,k]]\n",
    "        has = [[[float('inf')] * (k+1) for _ in range(n)] for __ in range(m)]\n",
    "        has[0][0], cnt = [0] * (k+1), 1\n",
    "        while dp:\n",
    "            ndp, dp = sorted(dp,key=lambda x:-x[2]), []\n",
    "            for x,y,p in ndp:\n",
    "                for nx,ny in [[x+1,y],[x,y+1],[x,y-1],[x-1,y]]:\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        if grid[nx][ny]:\n",
    "                            if p: np = p - 1\n",
    "                            else: continue\n",
    "                        else: np = p\n",
    "                        if has[nx][ny][np] > cnt:\n",
    "                            dp.append([nx,ny,np])\n",
    "                            while np >= 0 and has[nx][ny][np] > cnt:\n",
    "                                has[nx][ny][np] = cnt\n",
    "                                np -= 1\n",
    "            cnt += 1\n",
    "        return has[-1][-1][0] if has[-1][-1][0] != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        # 最多可以消除k个障碍物\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # if k > n + m - 1:\n",
    "        #     return m + n - 1\n",
    "        dist = [[[inf] * (k + 1) for _ in range(n)] for _ in range(m)]\n",
    "        dist[0][0][0] = 0\n",
    "        q = deque()\n",
    "        q.append((0, 0, 0))\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        while q:\n",
    "            x, y, cur = q.popleft()\n",
    "            if [x, y] == [m - 1, n - 1]:\n",
    "                return dist[x][y][cur] \n",
    "            \n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy            \n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    z = cur + grid[nx][ny]\n",
    "                    if z <= k and dist[nx][ny][z] > dist[x][y][cur] + 1:\n",
    "                        dist[nx][ny][z] = dist[x][y][cur] + 1\n",
    "                        q.append((nx, ny, z))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, g: List[List[int]], k: int) -> int:\n",
    "        m, n = len(g), len(g[0])\n",
    "        if m == n == 1: return 0\n",
    "        q = [(0, 0, 0, 0)]\n",
    "        vis = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]\n",
    "        while q:\n",
    "            dist, i, j, d = heappop(q)\n",
    "            if vis[i][j][d]: continue\n",
    "            vis[i][j][d] = True\n",
    "            for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and d + g[x][y] <= k:\n",
    "                    if x == m - 1 and y == n - 1: return dist + 1\n",
    "                    heappush(q, (dist + 1, x, y, d + g[x][y]))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        visited = [[[0 for x in range(k+1)] for y in range(len(grid[0]))] for z in range(len(grid)) ]\n",
    "        que = Queue()\n",
    "        que.put([0,0,0])\n",
    "        visited[0][0][0] = 1\n",
    "        res = 0\n",
    "        while que.qsize():\n",
    "            for i in range(que.qsize()):\n",
    "                x,y,z = que.get() #z对应锤子个数，分为0个锤子到n个锤子 n+1种情形\n",
    "\n",
    "                if x==len(grid)-1 and y==len(grid[0])-1:\n",
    "                    return res \n",
    "                if x>0:\n",
    "                    #判断障碍物\n",
    "                    if grid[x-1][y]:\n",
    "                        if z<k and not visited[x-1][y][z+1]:\n",
    "                            visited[x-1][y][z+1] =1\n",
    "                            que.put([x-1,y,z+1])\n",
    "                    else:\n",
    "                        if  not visited[x-1][y][z]:\n",
    "                            visited[x-1][y][z] =1\n",
    "                            que.put([x-1,y,z])\n",
    "                if y>0:\n",
    "                    if grid[x][y-1]:\n",
    "                        if  z<k and not visited[x][y-1][z+1]:\n",
    "                            visited[x][y-1][z+1] = 1\n",
    "                            que.put([x,y-1,z+1])\n",
    "                    else:\n",
    "                        if not visited[x][y-1][z]:\n",
    "                            visited[x][y-1][z] = 1\n",
    "                            que.put([x,y-1,z])\n",
    "                if x<len(grid)-1:\n",
    "                    if grid[x+1][y]:\n",
    "                        if  z<k and not visited[x+1][y][z+1]:\n",
    "                            visited[x+1][y][z+1] = 1\n",
    "                            que.put([x+1,y,z+1])\n",
    "                    else:\n",
    "                        if not visited[x+1][y][z]:\n",
    "                            visited[x+1][y][z] =1\n",
    "                            que.put([x+1,y,z])\n",
    "                if y<len(grid[0])-1:\n",
    "                    if grid[x][y+1]:\n",
    "                        if  z<k and  not visited[x][y+1][z+1]:\n",
    "                            visited[x][y+1][z+1] = 1\n",
    "                            que.put([x,y+1,z+1])\n",
    "                    else:\n",
    "                        if not visited[x][y+1][z]:\n",
    "                            visited[x][y+1][z] =1\n",
    "                            que.put([x,y+1,z])\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        #dis=[[float(\"inf\")]*(k+1) for _ in range(m*n)]\n",
    "       # for i in range(k+1):\n",
    "        #    dis[0][i]=0\n",
    "        heap=[]\n",
    "        hq.heappush(heap,[0,0,0])\n",
    "        vis=[[0]*(k+1) for _ in range(m*n)]\n",
    "        \n",
    "        while heap:\n",
    "            d,t,pos=hq.heappop(heap)\n",
    "            if vis[pos][t]==1:\n",
    "                continue\n",
    "            vis[pos][t]=1\n",
    "            x=pos//n\n",
    "            y=pos%n\n",
    "            if x==m-1 and y==n-1:\n",
    "                return d\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<m and 0<=y1<n:\n",
    "                    newp=x1*n+y1\n",
    "                    if grid[x1][y1]==0 and vis[newp][t]==0:\n",
    "                        hq.heappush(heap,[d+1,t,newp])\n",
    "                    elif grid[x1][y1]==1 and t+1<=k and vis[newp][t+1]==0  :\n",
    "                        hq.heappush(heap,[d+1,t+1,newp])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        if n == 1 and m == 1:\n",
    "            return 0\n",
    "        q = deque([(0, 0, 0, k)])\n",
    "        vis = [[[False for _ in range(k+1)] for _ in range(m)] for _ in range(n)]\n",
    "        vis[0][0][k] = True\n",
    "        while q:\n",
    "            i, j, step, left = q.popleft()\n",
    "            for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                di, dj = i + x, j + y\n",
    "                if di < 0 or di >= n or dj < 0 or dj >= m:\n",
    "                    continue\n",
    "                dx = left - grid[di][dj]\n",
    "                if dx >= 0 and not vis[di][dj][dx]:\n",
    "                    vis[di][dj][dx] = True\n",
    "                    if di == n - 1 and dj == m - 1:\n",
    "                        return step + 1\n",
    "                    q.append((di, dj, step+1, left - grid[di][dj]))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Stat:\n",
    "    def __init__(self, x, y, step, remain=0):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.step = step\n",
    "        self.remain = remain\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        if len(grid) == 1 and len(grid[0]) == 1:\n",
    "            return 0\n",
    "\n",
    "        def bfs(grid,k):\n",
    "            mp = [[ [ 0 for kk in range(k + 1) ] for j in range(len(grid[0])) ] for i in range(len(grid))]\n",
    "            dx = [0, 0, 1, -1]\n",
    "            dy = [1, -1, 0, 0]\n",
    "            que = queue.Queue()\n",
    "            start = Stat(0,0,0,k)\n",
    "            mp[0][0][k] = 1\n",
    "            que.put(start)\n",
    "            while not que.empty():\n",
    "                st = que.get()\n",
    "                x, y, step, remain = st.x, st.y, st.step, st.remain\n",
    "                for i in range(4):\n",
    "                    new_x = x + dx[i]\n",
    "                    new_y = y + dy[i]\n",
    "                    if new_x == len(grid)-1 and new_y == len(grid[0])-1:\n",
    "                        return step + 1\n",
    "                    if new_x >= len(grid) or new_y >= len(grid[0]) or new_x < 0 or new_y < 0:\n",
    "                        continue\n",
    "                    if mp[new_x][new_y][remain] == 1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if grid[new_x][new_y] == 1:\n",
    "                            if remain > 0 and mp[new_x][new_y][remain - 1] == 0:\n",
    "                                mp[new_x][new_y][remain - 1] = 1\n",
    "                                que.put(Stat(new_x, new_y, step + 1, remain - 1))\n",
    "                        else:\n",
    "                            mp[new_x][new_y][remain] = 1\n",
    "                            que.put(Stat(new_x, new_y, step + 1, remain))                            \n",
    "            return 0x3f3f3f3f\n",
    "                        \n",
    "                    \n",
    "\n",
    "        longest = bfs(grid, k)\n",
    "        if longest == 0x3f3f3f3f:\n",
    "            return -1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from pprint import pprint\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        q=deque()\n",
    "        q.append((0,0,k),)\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        b=0\n",
    "        path=[]\n",
    "        for i in range(m):\n",
    "            path.append([])\n",
    "            for z in range(n):\n",
    "                path[i].append([])\n",
    "                for j in range(k+1):\n",
    "                    path[i][z].append(-1)\n",
    "        #print(len(path),len(path[0]),len(path[0][0]))\n",
    "        while q:\n",
    "            cnt=len(q)\n",
    "            for i in range(cnt): \n",
    "                x,y,c=q.popleft()\n",
    "                if (x,y)==(m-1,n-1):\n",
    "                    return b\n",
    "                if path[x][y][c]!=-1:   continue\n",
    "                path[x][y][c]=b\n",
    "\n",
    "                for d in ((0,1),(0,-1),(1,0),(-1,0)):\n",
    "                    nx,ny=(x+d[0],y+d[1])\n",
    "                    if (0<=nx<m and 0<=ny<n) and (grid[nx][ny]==0 or c>=1):\n",
    "                        q.append((nx,ny,c-grid[nx][ny]),)\n",
    "            b+=1\n",
    "            #if b==12:   \n",
    "                #pprint(q)\n",
    "                #pprint(path)\n",
    "        return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def checkvisit(visited,v,k):\n",
    "    (nx,ny,rest) = v\n",
    "    for i in range(rest,k+1):\n",
    "        if (nx,ny,i) in visited:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self,grid:List[List[int]],k:int):\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if m == 1 and n ==1:\n",
    "            return 0\n",
    "        k = min(k,m+n-3)\n",
    "        visited = set([0,0,k])\n",
    "        q = [(0,0,k)]\n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            q1 = []\n",
    "            for x,y,rest in q:\n",
    "                for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                    nx,ny = x+dx,y+dy\n",
    "                    if 0 <= nx < m and 0<= ny < n:\n",
    "                        if grid[nx][ny] == 0 :\n",
    "                            if not checkvisit(visited, (nx, ny, rest),rest):\n",
    "                                if nx == m-1 and ny == n-1:\n",
    "                                    return step\n",
    "                                q1.append((nx,ny,rest))\n",
    "                                visited.add((nx,ny,rest))\n",
    "                        elif rest > 0 and not checkvisit(visited, (nx, ny, rest - 1),rest):\n",
    "                            q1.append((nx,ny,rest-1))\n",
    "                            visited.add((nx,ny,rest-1))\n",
    "            q = q1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == n == 1:\n",
    "            return 0\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        que = collections.deque()\n",
    "        que.append((0, 0, k))\n",
    "        vis = set()\n",
    "        ans = 1\n",
    "        while que:\n",
    "            length = len(que)\n",
    "            for _ in range(length):\n",
    "                x, y, z = que.popleft()\n",
    "                if (x, y, z) in vis:\n",
    "                    continue\n",
    "                vis.add((x, y, z))\n",
    "                for dx, dy in directions:\n",
    "                    mx, my = x + dx, y + dy\n",
    "                    if (mx, my) == (m - 1, n - 1):\n",
    "                        return ans\n",
    "                    if 0 <= mx < m and 0 <= my < n:  # 可以到达\n",
    "                        if grid[mx][my] == 0:\n",
    "                            que.append((mx, my, z))\n",
    "                        elif z:\n",
    "                            que.append((mx, my, z - 1))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRECTIONS = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        queue = deque([])\n",
    "        queue.append((0,0,min(m+n-2,k)-grid[0][0]))\n",
    "        vis = set()\n",
    "        vis.add((0,0,min(m+n-2,k)-grid[0][0]))\n",
    "        res = inf\n",
    "        step = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                x,y,count = queue.popleft()\n",
    "                if x==m-1 and y==n-1:\n",
    "                    return step\n",
    "                for i in DIRECTIONS:\n",
    "                    x_new = x+i[0]\n",
    "                    y_new = y+i[1]\n",
    "                    if 0<=x_new<m and 0<=y_new<n and count-grid[x_new][y_new]>=0 and (x_new,y_new,count+grid[x_new][y_new]) not in vis:\n",
    "                        vis.add((x_new,y_new,count-grid[x_new][y_new]))\n",
    "                        queue.append((x_new,y_new,count-grid[x_new][y_new]))\n",
    "            step+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DS = ((1, 0), (0, 1), (-1, 0), (0, -1))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: list[list[int]], k: int) -> int:\n",
    "        w = len(grid)\n",
    "        h = len(grid[0])\n",
    "        q = [(0, 0, 0, 0)]\n",
    "        vis = {(0, 0, 0)}\n",
    "        while len(q) != 0:\n",
    "            x, y, removed, step = q.pop(0)\n",
    "            if x == w - 1 and y == h - 1:\n",
    "                return step\n",
    "            for dx, dy in DS:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if nx < 0 or nx >= w or ny < 0 or ny >= h:\n",
    "                    continue\n",
    "                if grid[nx][ny] == 0:\n",
    "                    if (nx, ny, removed) in vis:\n",
    "                        continue\n",
    "                    vis.add((nx, ny, removed))\n",
    "                    q.append((nx, ny, removed, step + 1))\n",
    "                else:\n",
    "                    if removed == k or (nx, ny, removed + 1) in vis:\n",
    "                        continue\n",
    "                    vis.add((nx, ny, removed + 1))\n",
    "                    q.append((nx, ny, removed + 1, step + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        if not any(grid): return -1\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        k = min(k, m+n-3)\n",
    "        q = [(0, 0, k, 0)]\n",
    "        visited = {(0,0,k)}\n",
    "        while q:\n",
    "            x, y, rest, steps = q.pop(0)\n",
    "            if x == m-1 and y == n-1:\n",
    "                return steps\n",
    "            for nx, ny in [(x+1,y), (x-1,y), (x,y-1), (x,y+1)]:\n",
    "                if 0<=nx<m and 0<=ny<n:\n",
    "                    nk = rest-grid[nx][ny]\n",
    "                    if nk < 0 or (nx,ny,nk) in visited:\n",
    "                        continue\n",
    "                    q.append((nx,ny,nk,steps+1))\n",
    "                    visited.add((nx,ny,nk))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        from queue import Queue\n",
    "        que = Queue()\n",
    "        que.put((0, 0, k, 0), False)\n",
    "        visited = set((0, 0, k))\n",
    "        while not que.empty():\n",
    "            cur = que.get(False)\n",
    "            #print('visit:', cur)\n",
    "            if cur[0] == r - 1 and cur[1] == c - 1:\n",
    "                return cur[3]\n",
    "            if cur[0] > 0:\n",
    "                kk = cur[2]\n",
    "                if grid[cur[0] - 1][cur[1]] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and (cur[0] - 1, cur[1], kk) not in visited:\n",
    "                    que.put((cur[0] - 1, cur[1], kk, cur[3] + 1), False)\n",
    "                    visited.add((cur[0] - 1, cur[1], kk))\n",
    "            if cur[0] < r - 1:\n",
    "                kk = cur[2]\n",
    "                if grid[cur[0] + 1][cur[1]] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and (cur[0] + 1, cur[1], kk) not in visited:\n",
    "                    que.put((cur[0] + 1, cur[1], kk, cur[3] + 1), False)\n",
    "                    visited.add((cur[0] + 1, cur[1], kk))\n",
    "            if cur[1] > 0:\n",
    "                kk = cur[2]\n",
    "                if grid[cur[0]][cur[1] - 1] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and (cur[0], cur[1] - 1, kk) not in visited:\n",
    "                    que.put((cur[0], cur[1] - 1, kk, cur[3] + 1), False)\n",
    "                    visited.add((cur[0], cur[1] - 1, kk))\n",
    "            if cur[1] < c - 1:\n",
    "                kk = cur[2]\n",
    "                if grid[cur[0]][cur[1] + 1] == 1:\n",
    "                    kk -= 1\n",
    "                if kk >= 0 and (cur[0], cur[1] + 1, kk) not in visited:\n",
    "                    que.put((cur[0], cur[1] + 1, kk, cur[3] + 1), False)\n",
    "                    visited.add((cur[0], cur[1] + 1, kk))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        nRow = len(grid)\n",
    "        nCol = len(grid[0])\n",
    "\n",
    "        queue = deque()\n",
    "        queue.append((0, 0, k))\n",
    "        visited = set()\n",
    "        visited.add((0, 0, k))\n",
    "        curStep = 0\n",
    "\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                curRow, curCol, curK = queue.popleft()\n",
    "                if curRow == nRow - 1 and curCol == nCol - 1:\n",
    "                    return curStep\n",
    "\n",
    "                for curDir in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                    newRow = curRow + curDir[0]\n",
    "                    newCol = curCol + curDir[1]\n",
    "                    if 0 <= newRow < nRow and 0 <= newCol < nCol:\n",
    "                        if grid[newRow][newCol] == 0 and (newRow, newCol, curK) not in visited:\n",
    "                            visited.add((newRow, newCol, curK))\n",
    "                            queue.append((newRow, newCol, curK))\n",
    "                        elif grid[newRow][newCol] == 1 and curK > 0 and (newRow, newCol, curK - 1) not in visited:\n",
    "                            visited.add((newRow, newCol, curK - 1))\n",
    "                            queue.append((newRow, newCol, curK - 1))\n",
    "            curStep += 1\n",
    "        \n",
    "        return -1\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return 0\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        from collections import deque\n",
    "        queue = deque([])\n",
    "        queue.append((0, 0, k))\n",
    "        visited = set()\n",
    "        visited.add((0, 0, k))\n",
    "        step = 0\n",
    "        while queue:\n",
    "            step += 1\n",
    "            for _ in range(len(queue)):\n",
    "                row, col, reminder = queue.popleft()\n",
    "                for dr, dc in dirs:\n",
    "                    new_row, new_col = row + dr, col + dc\n",
    "                    if new_row < 0 or new_row >= m or new_col < 0 or new_col >= n:\n",
    "                        continue\n",
    "                    if new_row == m - 1 and new_col == n - 1:\n",
    "                        return step\n",
    "                    if grid[new_row][new_col] == 1 and reminder == 0:\n",
    "                        continue\n",
    "                    new_reminder = reminder - grid[new_row][new_col]\n",
    "                    if (new_row, new_col, new_reminder) in visited:\n",
    "                        continue\n",
    "                    visited.add((new_row, new_col, new_reminder))\n",
    "                    queue.append((new_row, new_col, new_reminder))\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        l = deque()\n",
    "        l.append([0,0,0,k])\n",
    "        arrived = set()\n",
    "\n",
    "        while l:\n",
    "            i,j,s,c = l.popleft()\n",
    "            if i == m-1 and j == n-1:\n",
    "                return s\n",
    "            for a,b in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                a = a+i\n",
    "                b = b+j\n",
    "                if a < 0 or a >= m or b < 0 or b >= n or c-grid[a][b] < 0:\n",
    "                    continue\n",
    "                if (a,b,c-grid[a][b]) not in arrived:\n",
    "                    arrived.add((a,b,c-grid[a][b]))\n",
    "                else:\n",
    "                    continue    \n",
    "                l.append([a,b,s+1,c-grid[a][b]])\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        dist = {(0,0,k):0}\n",
    "        d = deque([(0,0,k)])\n",
    "        while d:\n",
    "            x, y, j = d.popleft()\n",
    "            step = dist[(x,y,j)]\n",
    "            if x==m-1 and y==n-1:\n",
    "                return step\n",
    "            for dx, dy in dirs:\n",
    "                cx, cy = x+dx, y+dy\n",
    "                if 0<=cx<m and 0<=cy<n:\n",
    "                    if grid[cx][cy] == 0 and (cx,cy,j) not in dist:\n",
    "                        d.append((cx,cy,j))\n",
    "                        dist[(cx,cy,j)] = step + 1\n",
    "                    elif grid[cx][cy] == 1 and j and (cx,cy,j-1) not in dist:\n",
    "                        d.append((cx,cy,j-1))\n",
    "                        dist[(cx,cy,j-1)] = step + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        que = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        que.append(( 0, -k, 0, 0))    # (预估距离总和，当前开销, -当前剩余消除障碍次数, 行位置，列位置)\n",
    "        best_stat = {(0, 0, k) : 0}\n",
    "\n",
    "        while que:\n",
    "            cost, cur_k, i, j = que.pop(0)\n",
    "            cur_k = 0 - cur_k\n",
    "\n",
    "            if i == m-1 and j == n-1:\n",
    "                return cost\n",
    "\n",
    "            new_cost = cost + 1\n",
    "            for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if ii >= 0 and ii < m and jj >= 0 and jj < n:\n",
    "                    if grid[ii][jj] == 1:\n",
    "                        if cur_k > 0:\n",
    "                            new_k = cur_k - 1\n",
    "                        else:\n",
    "                            continue\n",
    "                    else:\n",
    "                        new_k = cur_k\n",
    "\n",
    "                    if (ii, jj, new_k) not in best_stat :\n",
    "                        best_stat[(ii, jj, new_k)] = new_cost\n",
    "                        que.append((new_cost, -new_k, ii, jj))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dis=[[float(\"inf\")]*(k+1) for _ in range(m*n)]\n",
    "        for i in range(k+1):\n",
    "            dis[0][i]=0\n",
    "        heap=[]\n",
    "        hq.heappush(heap,[0,0,0])\n",
    "        vis=[[0]*(k+1) for _ in range(m*n)]\n",
    "        \n",
    "        while heap:\n",
    "            d,t,pos=hq.heappop(heap)\n",
    "            if vis[pos][t]==1:\n",
    "                continue\n",
    "            vis[pos][t]=1\n",
    "            x=pos//n\n",
    "            y=pos%n\n",
    "            if x==m-1 and y==n-1:\n",
    "                return d\n",
    "\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<m and 0<=y1<n:\n",
    "                    newp=x1*n+y1\n",
    "                    if grid[x1][y1]==0 and vis[newp][t]==0:\n",
    "                        hq.heappush(heap,[d+1,t,newp])\n",
    "                    elif grid[x1][y1]==1 and t+1<=k and vis[newp][t+1]==0  :\n",
    "                        hq.heappush(heap,[d+1,t+1,newp])\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
